#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
#include<time.h>

using namespace std;
#define RED 1
#define BLACK 2

template<class K, class V>
struct RBTreeNode {//采用的是三叉链，存储的类型为pair<K,V>
    pair<K, V> _kv;
    RBTreeNode* _right;
    RBTreeNode* _left;
    RBTreeNode* _parent;
    int _color;

    //默认构造
    RBTreeNode(const pair<K, V>& kv = pair<K, V>())
        :_kv(kv)
        , _right(nullptr)
        , _left(nullptr)
        , _parent(nullptr)
        , _color(RED)
    {}

};


template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
    //成员
public:
    Node* _root;


public:
    RBTree()//默认构造
        :_root(nullptr)
    {}

    RBTree(const pair<K, V>& kv)//构造函数
        :_root(nullptr)
    {
        insert(kv);
    }



    int insert(const pair<K, V>& kv)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        //如果树中为空
        if (cur == nullptr) {//new一个节点后直接return返回
            _root = new Node(kv);
            _root->_color == BLACK;
            return true;
        }
        //如果不为空
        else {
            while (cur)//只要cur不为空就一直往下走,直到cur为空时，才是要插入的位置
            {
                if (kv.first > cur->_kv.first) {//如果插入的数比cur大，就放到右边
                    parent = cur;
                    cur = cur->_right;
                }
                else if (kv.first < cur->_kv.first) {//如果插入的数比cur小，就放到左边
                    parent = cur;
                    cur = cur->_left;
                }
                else {//如果插入的数相同了，直接return false
                    return false;
                }

                //当cur为空时，可以退出循环，准备插入工作
            }
            //插入cur
            Node* newnode = new Node(kv);
            if (kv.first > parent->_kv.first) { parent->_right = newnode; }//插入在右子树时
            else if (kv.first < parent->_kv.first) { parent->_left = newnode; }//插入在左子树时
            cur = newnode;
            cur->_parent = parent;
        }
        //至此，插入完成--------------------------------------------------------------------------
        //插入后，cur是新节点，parent是新节点的父节点

        while (parent && parent->_color == RED)
        {
            Node* grandfather = parent->_parent;
            //当parent是grandfather的左节点
            if (grandfather && parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_color == RED)//uncle存在并为红
                {
                    parent->_color = uncle->_color = BLACK;
                    grandfather->_color = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                    //继续往上判断
                }
                else//uncle不存在 或者 存在且为黑
                {
                    if (cur == parent->_right)//需要双旋
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_color = BLACK;
                        grandfather->_color = RED;
                    }
                    else//需要单旋
                    {
                        RotateR(grandfather);
                        parent->_color = BLACK;
                        grandfather->_color = RED;
                    }

                    break;
                }
            }
            //当parent是grandfather的右节点
            else if (grandfather && parent == grandfather->_right)
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_color == RED)//uncle存在并为红
                {
                    parent->_color = uncle->_color = BLACK;
                    grandfather->_color = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                    //继续往上判断
                }
                else//uncle不存在 或者 存在且为黑
                {
                    if (cur == parent->_left)//需要双旋
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_color = BLACK;
                        grandfather->_color = RED;
                    }
                    else//需要单旋
                    {
                        RotateL(grandfather);
                        parent->_color = BLACK;
                        grandfather->_color = RED;
                    }

                    break;
                }
            }
            else
                break;
        }

        _root->_color = BLACK;
    }
    bool print()
    {
        if (!_root) {
            printf("nullptr\n");
            return true;
        }
        vector<pair<K, V>> v;
        _print(_root, v);
        for (auto e : v) {
            cout << e.first << "_" << e.second << " ";
        }
        cout << endl;
        return true;
    }
    bool _print(Node* cur, vector<pair<K, V>>& v)
    {
        if (cur == nullptr)
            return true;

        _print(cur->_left, v);
        v.push_back(cur->_kv);
        _print(cur->_right, v);
        return true;
    }
    void RotateL(Node* Parent)//左单旋,具体原理看notie笔记
    {
        Node* parent = Parent;
        Node* cur = parent->_right;//左单旋，cur必定是parent的右边，具体画图理解

        parent->_right = cur->_left;
        if (cur->_left) {//如果cur的左子树有节点，就将左子树的父节点从cur变为parent
            cur->_left->_parent = parent;
        }
        cur->_left = parent;
        Node* ppnode = parent->_parent;
        if (parent == _root) {//parent为根节点时：
            _root = cur;
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        else
        {
            if (ppnode->_left == parent)//ppnode的左节点是parent
            {
                ppnode->_left = cur;
            }
            else if (ppnode->_right == parent)//ppnode的右节点是parent
            {
                ppnode->_right = cur;
            }
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
    }

    void RotateR(Node* Parent)//右单旋,具体原理看notie笔记
    {
        Node* parent = Parent;
        Node* cur = parent->_left;//右单旋，cur必定是parent的左边，具体画图理解

        parent->_left = cur->_right;
        if (cur->_right) {//如果cur的右子树有节点，就将右子树的父节点从cur变为parent
            cur->_right->_parent = parent;
        }
        cur->_right = parent;
        Node* ppnode = parent->_parent;
        if (parent == _root) {//parent为根节点时：
            _root = cur;
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        else
        {
            if (ppnode->_left == parent)//ppnode的左节点是parent
            {
                ppnode->_left = cur;
            }
            else if (ppnode->_right == parent)//ppnode的右节点是parent
            {
                ppnode->_right = cur;
            }
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
    }

    bool IsBanlance()
    {
        return IsBanlance(_root);
    }

    bool IsBanlance(Node* root)//注意: IsBanlance不是一个递归函数
    {
        //1.不能有连续的红节点
        //2.每个路劲的黑节点相同，设定一个基准值去比较
        if (root == nullptr)
            return true;
        if (root->_color != BLACK)//传入的只会是根节点，如果根节点不是黑节点则错误
            return false;


        //设置基准值
        int benchmark = 0;
        Node* cur = root;
        while (cur)
        {
            if (cur->_color == BLACK)
                benchmark++;
            cur = cur->_left;
        }

        return Checkcolor(root->_left, 1, benchmark) && Checkcolor(root->_right, 1, benchmark);
    }

    bool Checkcolor(Node* root, int blacknum, int benchmark)
    {
        if (root == nullptr)
        {
            //如果递归到空时，黑节点的数量与基准值对不上，则说明该树不为红黑树
            if (blacknum != benchmark)
            {
                cout << "黑节点的数量不对" << endl;
                return false;
            }
            return true;
        }
        //不能有连续的红节点
        if (root->_parent && root->_color == RED && root->_parent->_color == RED)
        {
            cout << "出现连续红节点" << endl;
            return false;
        }

        //遇到黑节点就对blacknum加加
        if (root->_color == BLACK)
            blacknum++;

        return Checkcolor(root->_left, blacknum, benchmark) &&
            Checkcolor(root->_right, blacknum, benchmark);
    }
};